The present invention is directed to ad-hoc wireless communication networks in which devices that are nodes on the wireless network compete for access to the frequency channel in order to communicate with each other.
One well known technique for controlling how devices access a shared channel is called ALOHA. In the ALOHA scheme, every node transmits as long as it has data available to transmit. If a collision is detected, the source node backs off and retransmits again after a timeout interval. An improvement to ALOHA is the so-called “slotted” ALOHA in which the transmitting node can only transmit within a slot boundary. However, collision probability is still high and unavoidable using the ALOHA schemes.
There are two other well known channel access protocols: Carrier Sense Multiple Access (CSMA) and Time Division Multiple Access (TDMA). The TDMA scheme is mainly used for transmission that has certain requirements that must be met to maintain reliability and minimal delay for signals carrying voice and video in which latency is an issue. The CSMA technique is mainly used for data transmissions where latency is not necessarily a concern.
Carrier Sense Multiple Access with Collision Detection (CSMA/CD) is a scheme in which the source node listens to the channel first to determine if the channel is free before it transmits. If the node determines that the channel is free, it transmits its data packet. The packet received by the intended recipient node is transmitted back to the source node where it is compared with the original packet. If the source node determines that the received packet does not match the transmitted packet, then it declares that a collision occurred and the source node backs off for a period of time and retransmits the packet.
An improvement to CSMA/CD is Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). In this scheme, the source node transmits when the channel is free. If the channel is not free, the source node waits until the end of a transmission on the channel and then waits again for a random period of time that is uniformly distributed between 0 and the duration of the time period during which nodes contend for access to the channel, known as the “contention window”. At the expiration of the contention window, the source node monitors activity on the channel again. If the source node determines that the channel is free, it transmits the packet. If the source node determines that the channel is not free, then the process repeats. A disadvantage of the CSMA/CS technique is that there is no guarantee that collisions will be avoided, particularly when there is a “hidden” node on the network.
Still another channel access scheme is called Distributed Foundation Wireless Medium Access Control (DFWMAC-IEEE 802.11). The IEEE 802.11 communication protocol is an industry standard that is based upon CSMA/CA but with the addition of handshaking control signals between the source node and destination node. The purpose of the handshaking protocol is to solve the hidden node problem. In this scheme, a source node wishing to transmit data first sends a Request to Send (RTS) message to the intended recipient or destination node. If the intended recipient node is ready to receive the data from the source node it responds with Clear to Send (CTS) message transmitted to the source node. Upon receiving a CTS message, the source node transmits the data packet to the intended recipient node. If the recipient node receives the data packet correctly, the recipient node transmits an acknowledgment (ACK) message to the source node so that the source node knows the transmission was successful. The exchange of RTS and CTS messages avoid the prolonged collisions since RTS and CTS messages are short control packets. In addition, the RTS/CTS/ACK scheme solves the hidden node problem because a source node only transmits when the recipient has indicated it is ready to receive. All other nodes that are not involved in the communication session between the source node and recipient node will listen and detect the RTS/CTS/ACK message exchange and know to back off the channel thereby avoiding the hidden node problem. If the source node does not receive an ACK from the recipient node, it doubles the duration of the contention window for the retransmission until a retransmission counter reaches a maximum value. The contention window is reset upon every successful transmission or when the retransmission counter has reached a maximum value.
There are also variations of the channel access control schemes of the IEEE 802.11 standard. One is the Five-Phase Reservation Protocol (FPRP) designed for scheduling broadcast messages. The FPRP uses synchronous timing operations and provides for additional control packet exchanges. Still another variation is to have separate control packets during both the signal period and data period for both unicast and broadcast messages. During the signaling period, data slots are reserved by the source node. However, immediately before the data period, additional packets are sent from the recipient node to confirm the reservation to the source node.
There are also some collision free protocols which are topology independent. For example, the utilization of Latin Squares and Time Spread Multiple Access (TSMA) codes produced from polynomials over Galois fields are used for slot and channel assignments. Utilizing these assigned slots, nodes can access the channel without colliding with transmission from other nodes.
Recently, channel access techniques have been developed that are known as Neighbor-Aware Contention Resolution (NCR) protocols such as Node Activation Multiple Access (NAMA) and Hybrid Activation Multiple Access (HAMA). These types of protocols assign a priority to each node or link based upon a hash function. The node or link with the highest priority among its two-hop neighbors can access the channel.
Even though the channel access schemes of the IEEE 802.11 standard helps solve the hidden node problem, it does not eliminate collisions because it is still a CSMA/CA scheme. For example, if multiple nodes have the same transmission time and happen to select the same random back-off time when the channel is not busy, their transmission will collide.
The collisions issue becomes more serious when the amount of traffic on the network increases. Heavy traffic increases the probability of at least two nodes trying to access the channel at the same time. Likewise, as the number of nodes on the network increases the probability of collisions also increases because more nodes are trying to access the channel.
The FPRP is not collision free and has other problems such as the “exposed terminal” problem. FPRP also does not work well with changing network topology. The collision-free protocols such as the Latin Squares and TSMA codes only work for small networks, and also require the maximum number of nodes and maximum degree of nodes in order to guarantee successful packet transmissions.
For NCR protocols, channels may be underutilized if a winning node has no packet to send. Access delays could also increase if a losing node has to wait to send a packet. In addition, the hash function used in the NCR protocols is based upon a pseudo-random number generator and is computationally expensive to implement in a device.